/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/max-points-on-a-line
   @Language: C++
   @Datetime: 16-02-09 05:59
   */

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */

class Solution {
public:
	/**
	 * @param points an array of point
	 * @return an integer
	 * Tip: select point i, and enum all point from i+1 to end,
	 *      calculat line slope k, count lines whose slope is k.
	 */
	int maxPoints(vector<Point>& PS) {
		// Write your code here
		unordered_map<float,int> hm;
		int maxp = 0;
		for(int i=0; i<PS.size(); ++i){
			int dup = 1;
			hm.clear();
			for(int j=i+1; j<PS.size(); ++j){
				if (PS[j].x==PS[i].x && PS[j].y==PS[i].y) ++dup;
				else if (PS[j].x==PS[i].x) ++hm[INT_MAX];
				else ++hm[(float)(PS[j].y-PS[i].y)/(PS[j].x-PS[i].x)];
			}
			for(const auto &k : hm)
				maxp = max(maxp,k.second+dup);
		}
		return (maxp==0 ? PS.size() : maxp);
	}
};
